Search results for "Binary strings"
showing 5 items of 5 documents
Algebraic and logical characterizations of deterministic linear time classes
1997
In this paper an algebraic characterization of the class DLIN of functions that can be computed in linear time by a deterministic RAM using only numbers of linear size is given. This class was introduced by Grandjean, who showed that it is robust and contains most computational problems that are usually considered to be solvable in deterministic linear time.
On Combinatorial Generation of Prefix Normal Words
2014
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on expe…
Combinatorial isomorphism between Fibonacci classes
2008
Abstract In 1985 Simion and Schmidt showed that the set S n (T 3) of length n permutations avoiding the set of patterns T 3={123, 132, 213} is counted by (the second order) Fibonacci numbers. They also presented a constructive bijection between the set F n–1 of length (n–1) binary strings with no two consecutive 1s and S n (T 3). In 2005, Egge and Mansour generalized the first Simion-Simion’s result and showed that S n (T p ), the set of permutations avoiding the patterns T p ={12…p, 132, 213}, is counted by the (p–1)th order Fibonacci numbers. In this paper we extend the second Simion-Schmidt’s result by giving a bijection between the set of length (n–1) binary strings with no (p–1) consec…
A trace partitioned Gray code forq-ary generalized Fibonacci strings
2015
AbstractWe provide a trace partitioned Gray code for the set of q-ary strings avoiding a pattern constituted by k consecutive equal symbols. The definition of this Gray code is based on two different constructions, according to the parity of q. This result generalizes, and is based on, a Gray code for binary strings avoiding k consecutive 0's.
A loop-free two-close Gray-code algorithm for listing k-ary Dyck words
2006
AbstractP. Chase and F. Ruskey each published a Gray code for length n binary strings with m occurrences of 1, coding m-combinations of n objects, which is two-close—that is, in passing from one binary string to its successor a single 1 exchanges positions with a 0 which is either adjacent to the 1 or separated from it by a single 0. If we impose the restriction that any suffix of a string contains at least k−1 times as many 0's as 1's, we obtain k-suffixes: suffixes of k-ary Dyck words. Combinations are retrieved as special case by setting k=1 and k-ary Dyck words are retrieved as a special case by imposing the additional condition that the entire string has exactly k−1 times as many 0's a…